package com.company.algo.tree.BST;

import com.company.algo.pojo.TreeNode;

import java.util.LinkedList;
import java.util.List;

//构建不同的二叉树
public class BuildBSTs {
    /* 主函数 */
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new LinkedList<>();
        //构造闭区间[1,n]组成的BST
        return build(1,n);
    }

    //紧扣定义：构造闭区间[1,n]组成的BSTs
    private List<TreeNode> build(int lo, int hi) {
        List<TreeNode> res = new LinkedList<>();
        //base case
        if (lo > hi) {
            res.add(null);
            return res;
        }
        //穷举root节点(i)的所有的可能
        for (int i = lo; i <= hi; i++) {
            List<TreeNode> leftTrees = build(lo, i - 1);
            List<TreeNode> rightTrees = build(i+1, hi);
            for(TreeNode left: leftTrees){
                for (TreeNode right:rightTrees){
                    //i作为根节点
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    res.add(root);
                }
            }

        }
        return res;
    }

}
